package com.ww.springboot.boot.algorithm.heap;

/**
 * 描述：大顶堆
 *
 * @author wanwei
 * @since 2021-06-17 17:55
 */
public class BigTopHeap {

    int size = 0;
    int[] nums;

    public int lastStoneWeight(int[] stones) {
        nums = new int[stones.length];
        for (int n : stones) {
            insert(n);
        }
        while (size > 1) {
            int x = pop();
            int y = pop();
            if (x != y) {
                insert(Math.abs(x - y));
            }
        }
        return size == 0 ? 0 : nums[0];
    }

    public void insert(int data) {
        nums[size++] = data;
        int father = size / 2, child = size;
        while (father > 0) {
            if (nums[father - 1] < data) {
                int temp = nums[father - 1];
                nums[father - 1] = data;
                nums[child - 1] = temp;
                child = father;
                father /= 2;
            } else {
                break;
            }
        }
    }

    public int pop() {
        int res = nums[0];
        nums[0] = nums[--size];
        int father = 0;
        while (father < size) {
            int left = 2 * father + 1, right = 2 * father + 2;
            if (left < size) {
                int max = left;
                if (right < size && nums[left] < nums[right]) {
                    max = right;
                }
                if (nums[father] < nums[max]) {
                    int temp = nums[father];
                    nums[father] = nums[max];
                    nums[max] = temp;
                    father = max;
                } else {
                    break;
                }
            } else {
                break;
            }
        }
        return res;
    }
}
